package com.linchong.dynamicprogramming.hard;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-19 13:51
 * @Description: BuySellStockIII$188-买卖股票的最佳时机4-https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
 */
public class BuySellStockIV {


	/**
	 *
	 *给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
	 *
	 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
	 *
	 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
	 *
	 *  
	 *
	 * 示例 1：
	 *
	 * 输入：k = 2, prices = [2,4,1]
	 * 输出：2
	 * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
	 * 示例 2：
	 *
	 * 输入：k = 2, prices = [3,2,6,5,0,3]
	 * 输出：7
	 * 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
	 *      随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
	 *  
	 *
	 * 提示：
	 *
	 * 0 <= k <= 109
	 * 0 <= prices.length <= 1000
	 * 0 <= prices[i] <= 1000
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
	 *
	 * 【分析】
	 *  如果K很大，K>N/2,题目可以简化为任意次买卖，即BuySellStockII,如果K>N/2,连续的上升可以收尾结合视为一个，其他不
	 *  连续的直接买上升
	 *
	 *  BuySellStockIII相当于K=2
	 *
	 *  同样，记录阶段，
	 *
	 *     第一次买之前(1)，持有股票(2)，第一次卖之后，第二次买之前(3)，持有股票(4)，...，第K次卖之后(2K+1)...
	 *     阶段1： 没买卖过
	 *     阶段3：买卖过一次
	 *     阶段5：买卖过两次
	 *     ...
	 *     阶段2K+1:买卖过K次，现在空仓
	 *
	 *  转移方程：
	 *  f[i][j]:前i（第i-1天）天结束后,处于j阶段获利最大
	 *   阶段1,3,5,...2k+1：
	 *      f[i][j] = max{f[i-1][j],f[i-1][j]+(P（i-1）-P（i-2）)}
	 *
	 * 	 阶段2,4,...,2k：
	 * 	    f[i][j] = max{f[i-1][j]+(P（i-1）-P（i-2）),f[i-1][j-1],f[i-1][j-2]+(P（i-1）-P（i-2）)}
	 *
	 *
	 *  初始化条件和边界情况
	 *       刚开始（前0天）处于阶段1
	 * 	 *      * f[0][1] = 0
	 * 	 *      * f[0][2]=f[0][3]=f[0][4]=f[0][5]=...=f[0][2k+1]=负无穷
	 * 	 *
	 * 	 *      阶段1,3,5,...,2K+1：f[i][j] = max{f[i-1][j],f[i-1][j]+(P（i-1）-P（i-2）)}
	 * 	 *
	 * 	 *      阶段2,4,...,2k：f[i][j] = max{f[i-1][j]+(P（i-1）-P（i-2）),f[i-1][j-1],f[i-1][j-2]+(P（i-1）-P（i-2）)}
	 * 	 *
	 * 	 *      如果j-1<1或j-2<1或i-2<0,对应项不计入max,即下标负数没有意义
	 * 	 因为最多买卖两次，所以答案是Max{f[N][1],f[N][3],...,f[N][2k+1]},即清仓状态下最后一天的最大获利
	 *
	 * step 4:计算顺序
	 * 	 *      初始化f[0][1],...,f[0][2k+1]
	 * 	 *      f[1][1],...,f[1][5]
	 * 	 *      ...
	 * 	 *      f[N][1],...,f[N][2k+1]
	 * 	 *      时间复杂度：O(NK),空间复杂度：O(NK),优化后可以O(K),因为f[i][1...2k+1]只依赖于f[i-1][1...2K+1]
	 */

	public int maxProfit(int[] prices,int k) {

		int n = prices.length;
		if(n == 0){
			return 0;
		}
		if(k>n/2){
			int result = 0;
			for (int i = 0; i < n-1; i++) {
				result += Math.max(prices[i+1]-prices[i],0);
			}
			return result;
		}


		int[][] f = new int[n+1][2*k+1+1];

		//init
		// 初始化前0天第一阶段最大获利是0
		f[0][1] = 0;
		for (int i = 2; i <= 2 * k + 1; i++) {
			f[0][i] = Integer.MIN_VALUE;
		}

		for (int i = 1; i <= n ; i++) {
			// 1,3,5
			for (int j = 1; j <=2*k+1 ; j+=2) {
				// f[i][j] = max{f[i-1][j],f[i-1][j]+(P（i-1）-P（i-2）)}
				f[i][j] = f[i-1][j];
				// 负无穷+负数=正数
				if(j>1 && i>1&&f[i-1][j-1]!=Integer.MIN_VALUE){
					f[i][j] = Math.max(f[i][j],f[i-1][j-1]+prices[i-1]-prices[i-2]);
				}

			}

			for (int j = 2; j <= 2*k+1; j+=2) {
				//max{f[i-1][j]+(P（i-1）-P（i-2）),f[i-1][j-1],f[i-1][j-2]+(P（i-1）-P（i-2）)}
				f[i][j] = f[i-1][j-1];
				if(i>1 && f[i-1][j]!=Integer.MIN_VALUE){
					f[i][j] = Math.max(f[i][j],f[i-1][j]+prices[i-1]-prices[i-2]);
				}

				if(j>2 && i>1 &&f[i-1][j-2]!=Integer.MIN_VALUE){
					f[i][j] = Math.max(f[i][j],f[i-1][j-2]+prices[i-1]-prices[i-2]);
				}

			}
		}

		int res = Integer.MIN_VALUE;
		for (int i = 1; i <= 2*k+1; i+=2) {
			res = Math.max(res,f[n][i]);
		}
		return res;
	}
	public static void main(String[] args) {

		int[] prices = {2,1,4,5,2,9,7};
		BuySellStockIV instance = new BuySellStockIV();
		System.out.println(instance.maxProfit(prices,2));

	}
}
